Implicational propositional calculus

From HandWiki

In mathematical logic, the implicational propositional calculus is a version of classical propositional calculus that uses only one connective, called implication or conditional. In formulas, this binary operation is indicated by "implies", "if ..., then ...", "→", "[math]\displaystyle{ \rightarrow }[/math]", etc..

Functional (in)completeness

Implication alone is not functionally complete as a logical operator because one cannot form all other two-valued truth functions from it.

For example, the two-place truth function that always returns false is not definable from → and arbitrary propositional variables: any formula constructed from → and propositional variables must receive the value true when all of its variables are evaluated to true. It follows that {→} is not functionally complete.

However, if one adds a nullary connective ⊥ for falsity, then one can define all other truth functions. Formulas over the resulting set of connectives {→, ⊥} are called f-implicational.[1] If P and Q are propositions, then:

  • ¬P is equivalent to P → ⊥
  • P ∧ Q is equivalent to (P → (Q → ⊥)) → ⊥
  • P ∨ Q is equivalent to (P → Q) → Q
  • P ↔ Q is equivalent to ((P → Q) → ((Q → P) → ⊥)) → ⊥

Since the above operators are known to be functionally complete, it follows that any truth function can be expressed in terms of → and ⊥.

Axiom system

The following statements are considered tautologies (irreducible and intuitively true, by definition).

Where in each case, P, Q, and R may be replaced by any formulas that contain only "→" as a connective. If Γ is a set of formulas and A a formula, then [math]\displaystyle{ \Gamma\vdash A }[/math] means that A is derivable using the axioms and rules above and formulas from Γ as additional hypotheses.

Łukasiewicz (1948) found an axiom system for the implicational calculus that replaces the schemas 1–3 above with a single schema

  • ((P → Q) → R) → ((R → P) → (S → P)).

He also argued that there is no shorter axiom system.

Basic properties of derivation

Since all axioms and rules of the calculus are schemata, derivation is closed under substitution:

If [math]\displaystyle{ \Gamma\vdash A, }[/math] then [math]\displaystyle{ \sigma(\Gamma)\vdash\sigma(A), }[/math]

where σ is any substitution (of formulas using only implication).

The implicational propositional calculus also satisfies the deduction theorem:

If [math]\displaystyle{ \Gamma,A\vdash B }[/math], then [math]\displaystyle{ \Gamma\vdash A\to B. }[/math]

As explained in the deduction theorem article, this holds for any axiomatic extension of the system containing axiom schemas 1 and 2 above and modus ponens.

Completeness

The implicational propositional calculus is semantically complete with respect to the usual two-valued semantics of classical propositional logic. That is, if Γ is a set of implicational formulas, and A is an implicational formula entailed by Γ, then [math]\displaystyle{ \Gamma\vdash A }[/math].

Proof

A proof of the completeness theorem is outlined below. First, using the compactness theorem and the deduction theorem, we may reduce the completeness theorem to its special case with empty Γ, i.e., we only need to show that every tautology is derivable in the system.

The proof is similar to completeness of full propositional logic, but it also uses the following idea to overcome the functional incompleteness of implication. If A and F are formulas, then A → F is equivalent to (¬A*) ∨ F, where A* is the result of replacing in A all, some, or none of the occurrences of F by falsity. Similarly, (A → F) → F is equivalent to A* ∨ F. So under some conditions, one can use them as substitutes for saying A* is false or A* is true respectively.

We first observe some basic facts about derivability:

[math]\displaystyle{ A\to B,B\to C\vdash A\to C }[/math]

 

 

 

 

(1)

Indeed, we can derive A → (B → C) using Axiom 1, and then derive A → C by modus ponens (twice) from Ax. 2.

[math]\displaystyle{ A\to B\vdash(B\to C)\to(A\to C) }[/math]

 

 

 

 

(2)

This follows from (1) by the deduction theorem.

[math]\displaystyle{ A\to C,(A\to B)\to C\vdash C }[/math]

 

 

 

 

(3)

If we further assume C → B, we can derive A → B using (1), then we derive C by modus ponens. This shows [math]\displaystyle{ A\to C,(A\to B)\to C,C\to B\vdash C }[/math], and the deduction theorem gives [math]\displaystyle{ A\to C,(A\to B)\to C\vdash(C\to B)\to C }[/math]. We apply Ax. 3 to obtain (3).

Let F be an arbitrary fixed formula. For any formula A, we define A0 = (A → F) and A1 = ((A → F) → F). Consider only formulas in propositional variables p1, ..., pn. We claim that for every formula A in these variables and every truth assignment e,

[math]\displaystyle{ p_1^{e(p_1)},\dots,p_n^{e(p_n)}\vdash A^{e(A)}. }[/math]

 

 

 

 

(4)

We prove (4) by induction on A. The base case A = pi is trivial. Let A = (B → C). We distinguish three cases:

  1. e(C) = 1. Then also e(A) = 1. We have
    [math]\displaystyle{ (C\to F)\to F\vdash((B\to C)\to F)\to F }[/math]
    by applying (2) twice to the axiom C → (B → C). Since we have derived (C → F) → F by the induction hypothesis, we can infer ((B → C) → F) → F.
  2. e(B) = 0. Then again e(A) = 1. The deduction theorem applied to (3) gives
    [math]\displaystyle{ B\to F\vdash((B\to C)\to F)\to F. }[/math]
    Since we have derived B → F by the induction hypothesis, we can infer ((B → C) → F) → F.
  3. e(B) = 1 and e(C) = 0. Then e(A) = 0. We have
    [math]\displaystyle{ \begin{align}(B\to F)\to F,C\to F,B\to C&\vdash B\to F&&\text{by (1)}\\&\vdash F&&\text{by modus ponens,}\end{align} }[/math]
    thus [math]\displaystyle{ (B\to F)\to F,C\to F\vdash(B\to C)\to F }[/math] by the deduction theorem. We have derived (B → F) → F and C → F by the induction hypothesis, hence we can infer (B → C) → F. This completes the proof of (4).

Now let F be a tautology in variables p1, ..., pn. We will prove by reverse induction on k = n,...,0 that for every assignment e,

[math]\displaystyle{ p_1^{e(p_1)},\dots,p_k^{e(p_k)}\vdash F. }[/math]

 

 

 

 

(5)

The base case k = n follows from a special case of (4) using

[math]\displaystyle{ F^{e(F)} = F^1 = ((F \to F) \to F) }[/math]

and the fact that F→F is a theorem by the deduction theorem.

Assume that (5) holds for k + 1, we will show it for k. By applying deduction theorem to the induction hypothesis, we obtain

[math]\displaystyle{ \begin{align}p_1^{e(p_1)},\dots,p_k^{e(p_k)}&\vdash(p_{k+1}\to F)\to F,\\ p_1^{e(p_1)},\dots,p_k^{e(p_k)}&\vdash((p_{k+1}\to F)\to F)\to F,\end{align} }[/math]

by first setting e(pk+1) = 0 and second setting e(pk+1) = 1. From this we derive (5) using modus ponens.

For k = 0 we obtain that the tautology F is provable without assumptions. This is what was to be proved.

This proof is constructive. That is, given a tautology, one could actually follow the instructions and create a proof of it from the axioms. However, the length of such a proof increases exponentially with the number of propositional variables in the tautology, hence it is not a practical method for any but the very shortest tautologies.

The Bernays–Tarski axiom system

The Bernays–Tarski axiom system is often used. In particular, Łukasiewicz's paper derives the Bernays–Tarski axioms from Łukasiewicz's sole axiom as a means of showing its completeness.
It differs from the axiom schemas above by replacing axiom schema 2, (P→(Q→R))→((P→Q)→(P→R)), with

  • Axiom schema 2': (P→Q)→((Q→R)→(P→R)),

which is called hypothetical syllogism. This makes derivation of the deduction meta-theorem a little more difficult, but it can still be done.

We show that from P→(Q→R) and P→Q one can derive P→R. This fact can be used in lieu of axiom schema 2 to get the meta-theorem.

  1. P→(Q→R) given
  2. P→Q given
  3. (P→Q)→((Q→R)→(P→R)) ax 2'
  4. (Q→R)→(P→R) mp 2,3
  5. (P→(Q→R))→(((Q→R)→(P→R))→(P→(P→R))) ax 2'
  6. ((Q→R)→(P→R))→(P→(P→R)) mp 1,5
  7. P→(P→R) mp 4,6
  8. (P→(P→R))→(((P→R)→R)→(P→R)) ax 2'
  9. ((P→R)→R)→(P→R) mp 7,8
  10. (((P→R)→R)→(P→R))→(P→R) ax 3
  11. P→R mp 9,10 qed

Satisfiability and validity

Main pages: Tautology (logic)#Efficient verification and the Boolean satisfiability problem  and Boolean satisfiability problem#Algorithms for solving SAT

Satisfiability in the implicational propositional calculus is trivial, because every formula is satisfiable: just set all variables to true.

Falsifiability in the implicational propositional calculus is NP-complete,[2] meaning that validity (tautology) is co-NP-complete.

In this case, a useful technique is to presume that the formula is not a tautology and attempt to find a valuation that makes it false. If one succeeds, then it is indeed not a tautology. If one fails, then it is a tautology.

Example of a non-tautology:

Suppose [(A→B)→((C→A)→E)]→([F→((C→D)→E)]→[(A→F)→(D→E)]) is false.

Then (A→B)→((C→A)→E) is true; F→((C→D)→E) is true; A→F is true; D is true; and E is false.

Since D is true, C→D is true. So the truth of F→((C→D)→E) is equivalent to the truth of F→E.

Then since E is false and F→E is true, we get that F is false.

Since A→F is true, A is false. Thus A→B is true and (C→A)→E is true.

C→A is false, so C is true.

The value of B does not matter, so we can arbitrarily choose it to be true.

Summing up, the valuation that sets B, C and D to be true and A, E and F to be false will make [(A→B)→((C→A)→E)]→([F→((C→D)→E)]→[(A→F)→(D→E)]) false. So it is not a tautology.

Example of a tautology:

Suppose ((A→B)→C)→((C→A)→(D→A)) is false.

Then (A→B)→C is true; C→A is true; D is true; and A is false.

Since A is false, A→B is true. So C is true. Thus A must be true, contradicting the fact that it is false.

Thus there is no valuation that makes ((A→B)→C)→((C→A)→(D→A)) false. Consequently, it is a tautology.

Adding an axiom schema

What would happen if another axiom schema were added to those listed above? There are two cases: (1) it is a tautology; or (2) it is not a tautology.

If it is a tautology, then the set of theorems remains the set of tautologies as before. However, in some cases it may be possible to find significantly shorter proofs for theorems. Nevertheless, the minimum length of proofs of theorems will remain unbounded, that is, for any natural number n there will still be theorems that cannot be proved in n or fewer steps.

If the new axiom schema is not a tautology, then every formula becomes a theorem (which makes the concept of a theorem useless in this case). What is more, there is then an upper bound on the minimum length of a proof of every formula, because there is a common method for proving every formula. For example, suppose the new axiom schema were ((B→C)→C)→B. Then ((A→(A→A))→(A→A))→A is an instance (one of the new axioms) and also not a tautology. But [((A→(A→A))→(A→A))→A]→A is a tautology and thus a theorem due to the old axioms (using the completeness result above). Applying modus ponens, we get that A is a theorem of the extended system. Then all one has to do to prove any formula is to replace A by the desired formula throughout the proof of A. This proof will have the same number of steps as the proof of A.

An alternative axiomatization

The axioms listed above primarily work through the deduction metatheorem to arrive at completeness. Here is another axiom system that aims directly at completeness without going through the deduction metatheorem.

First we have axiom schemas that are designed to efficiently prove the subset of tautologies that contain only one propositional variable.

  • aa 1: ꞈA→A
  • aa 2: (A→B)→ꞈ(A→(C→B))
  • aa 3: A→((B→C)→ꞈ((A→B)→C))
  • aa 4: A→ꞈ(B→A)

The proof of each such tautology would begin with two parts (hypothesis and conclusion) that are the same. Then insert additional hypotheses between them. Then insert additional tautological hypotheses (which are true even when the sole variable is false) into the original hypothesis. Then add more hypotheses outside (on the left). This procedure will quickly give every tautology containing only one variable. (The symbol "ꞈ" in each axiom schema indicates where the conclusion used in the completeness proof begins. It is merely a comment, not a part of the formula.)

Consider any formula Φ that may contain A, B, C1, ..., Cn and ends with A as its final conclusion. Then we take

  • aa 5: Φ−→(Φ+→ꞈΦ)

as an axiom schema where Φ− is the result of replacing B by A throughout Φ and Φ+ is the result of replacing B by (A→A) throughout Φ. This is a schema for axiom schemas since there are two level of substitution: in the first Φ is substituted (with variations); in the second, any of the variables (including both A and B) may be replaced by arbitrary formulas of the implicational propositional calculus. This schema allows one to prove tautologies with more than one variable by considering the case when B is false Φ− and the case when B is true Φ+.

If the variable that is the final conclusion of a formula takes the value true, then the whole formula takes the value true regardless of the values of the other variables. Consequently if A is true, then Φ, Φ−, Φ+ and Φ−→(Φ+→Φ) are all true. So without loss of generality, we may assume that A is false. Notice that Φ is a tautology if and only if both Φ− and Φ+ are tautologies. But while Φ has n+2 distinct variables, Φ− and Φ+ both have n+1. So the question of whether a formula is a tautology has been reduced to the question of whether certain formulas with one variable each are all tautologies. Also notice that Φ−→(Φ+→Φ) is a tautology regardless of whether Φ is, because if Φ is false then either Φ− or Φ+ will be false depending on whether B is false or true.

Examples:

Deriving Peirce's law

  1. [((P→P)→P)→P]→([((P→(P→P))→P)→P]→[((P→Q)→P)→P]) aa 5
  2. P→P aa 1
  3. (P→P)→((P→P)→(((P→P)→P)→P)) aa 3
  4. (P→P)→(((P→P)→P)→P) mp 2,3
  5. ((P→P)→P)→P mp 2,4
  6. [((P→(P→P))→P)→P]→[((P→Q)→P)→P] mp 5,1
  7. P→(P→P) aa 4
  8. (P→(P→P))→((P→P)→(((P→(P→P))→P)→P)) aa 3
  9. (P→P)→(((P→(P→P))→P)→P) mp 7,8
  10. ((P→(P→P))→P)→P mp 2,9
  11. ((P→Q)→P)→P mp 10,6 qed

Deriving Łukasiewicz' sole axiom

  1. [((P→Q)→P)→((P→P)→(S→P))]→([((P→Q)→(P→P))→(((P→P)→P)→(S→P))]→[((P→Q)→R)→((R→P)→(S→P))]) aa 5
  2. [((P→P)→P)→((P→P)→(S→P))]→([((P→(P→P))→P)→((P→P)→(S→P))]→[((P→Q)→P)→((P→P)→(S→P))]) aa 5
  3. P→(S→P) aa 4
  4. (P→(S→P))→(P→((P→P)→(S→P))) aa 2
  5. P→((P→P)→(S→P)) mp 3,4
  6. P→P aa 1
  7. (P→P)→((P→((P→P)→(S→P)))→[((P→P)→P)→((P→P)→(S→P))]) aa 3
  8. (P→((P→P)→(S→P)))→[((P→P)→P)→((P→P)→(S→P))] mp 6,7
  9. ((P→P)→P)→((P→P)→(S→P)) mp 5,8
  10. [((P→(P→P))→P)→((P→P)→(S→P))]→[((P→Q)→P)→((P→P)→(S→P))] mp 9,2
  11. P→(P→P) aa 4
  12. (P→(P→P))→((P→((P→P)→(S→P)))→[((P→(P→P))→P)→((P→P)→(S→P))]) aa 3
  13. (P→((P→P)→(S→P)))→[((P→(P→P))→P)→((P→P)→(S→P))] mp 11,12
  14. ((P→(P→P))→P)→((P→P)→(S→P)) mp 5,13
  15. ((P→Q)→P)→((P→P)→(S→P)) mp 14,10
  16. [((P→Q)→(P→P))→(((P→P)→P)→(S→P))]→[((P→Q)→R)→((R→P)→(S→P))] mp 15,1
  17. (P→P)→((P→(S→P))→[((P→P)→P)→(S→P)]) aa 3
  18. (P→(S→P))→[((P→P)→P)→(S→P)] mp 6,17
  19. ((P→P)→P)→(S→P) mp 3,18
  20. (((P→P)→P)→(S→P))→[((P→Q)→(P→P))→(((P→P)→P)→(S→P))] aa 4
  21. ((P→Q)→(P→P))→(((P→P)→P)→(S→P)) mp 19,20
  22. ((P→Q)→R)→((R→P)→(S→P)) mp 21,16 qed

Using a truth table to verify Łukasiewicz' sole axiom would require consideration of 16=24 cases since it contains 4 distinct variables. In this derivation, we were able to restrict consideration to merely 3 cases: R is false and Q is false, R is false and Q is true, and R is true. However because we are working within the formal system of logic (instead of outside it, informally), each case required much more effort.

See also

References

  1. ↑ Francola, John; Goldsmith, Judy; Schlipf, John; Speckenmeyer, Ewald; Swaminathan, R.P. (1999). "An algorithm for the class of pure implicational formulas". Discrete Applied Mathematics 96-97: 89–106. doi:10.1016/S0166-218X(99)00038-4. 
  2. ↑ Heusch, Peter (1999). "The complexity of the falsifiability problem for pure implicational formulas". Discrete Applied Mathematics 96-97: 127–138. doi:10.1016/S0166-218X(99)00036-0. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Implicational_propositional_calculus&oldid=3381387"